Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра СКС
Звіт
з лабораторної роботи № 2
з дисципліни: “Дискретна матетематика”
на тему: “ Задача про кістякове дерево екстремальної (мінімальної або максимальної) ваги
”
Мета: навчитися створювати програму яка обчислює задачу про кістякове дерево екстремальної (мінімальної або максимальної) ваги
Теоретичні відомості
При знаходженні кістякового дерева графа підхід із відкиданням ребер не є ефективним через те, що складно перевіряти наявність циклів в утворюваному графі.
Ефективним є підхід із конструюванням (утворенням) кістяка. У цьому разі просто перевіряти наявність циклів в графі, що виникає.
Вказаний підхід реалізує алгоритм Пріма (так званий алгоритм найближчого сусіда).
Крок 1. Присвоєння початкових значень.
S'={Xα}, Xα - довільна вершина графа (скажімо, перша за номером).
S''= S\S', V' = Ø
Крок 2. Оновлення даних.
Знаходимо таке ребро (Xi, Xj), що Xi ϵ S', Xj ϵ S'' та
W(Xi, Xj)= min{ W(Xα, Xβ)| Xα ϵ S', Xβ ϵ S''}
Покладаємо S' = S' U { Xi }, S'' = S\S', V' = V'U{(Xi, Xj)}
Крок 3. Перевірка на завершення.
Якщо S' = S, то G' = (S', V') - шуканий граф.
В іншому випадку переходимо на Крок 2.
Далі наведено приклад виконання алгоритму Пріма.
Граф задано списком ребер з вказанням їх ваг.
(1,4|1), (4,1|1), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,4|5),
(4,2|5), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (4,5|2), (5,4|2).
Відповідний цьому списку граф
Спершу впорядковуємо ребра за зростанням їх ваг. Для цього слід використати якийсь алгоритм сортування.
(1,4|1), (4,1|1), (4,5|2), (5,4|2), (1,5|3), (5,1|3), (2,3|3),
(3,2|3), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (2,4|5), (4,2|5).
Тепер власне виконуємо алгоритм Пріма (додаючи для кожного кроку 2 ребро мінімальної ваги).
S = {1,2,3,4,5}
Крок 1. S' = {1} S'' = {2,3,4,5} V' = Ø
Крок 2 . V' = V'U{(1,4|1)}={(1,4|1)}
S' = {1,4} S'' = {2,3,5}
Крок 3. S'≠S
Крок 2. V' = V'U{4,5|2} = {(1,4|1), (4,5|2)}
Крок 3. S'≠S
Крок 2. V' = V'U {(5,2|4)} = {(1,4|1), (4,5|2), (5,2|4)}
S' = {1,2,4,5} S'' = {3}
Крок 3. S'≠S
Крок 2. V' = V'U {(2,3|3)} = {(1,4|1), (4,5|2), (5,2|4), (2,3|3)}
S' = {1,2,3,4,5} S'' = Ø
Крок 3. S'=S
Таким чином, отримали таке кістякове дерево мінімальної ваги для початкового графа.
Вага отриманого кістякового дерева дорівнює 10.
Код програми мовою Delphi:
unit Pasik;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Buttons, Grids;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Label1: TLabel;
BitBtn2: TBitBtn;
Label2: TLabel;
procedure FormCreate(Sender: TObject);
procedure FormPaint(Sender: TObject);
procedure DrawLine(a1,a2,c: integer);
procedure StringGrid1SetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String);
procedure BitBtn2Click(Sender: TObject);
procedure DrawGraph;
private
{ Private declarations }
public
{ Public declarations }
end;
TMyPoint=record
x:integer;
y:integer;
name:string
end;
var
Form1: TForm1;
MyPoint:array[1..5] of TMyPoint;
koef:integer;
implementation
{$R *.dfm}
procedure TForm1.DrawGraph;
var
x,kx,ky,a,b:integer;
begin
Form1.Refresh;
for x:=1 to 5 do
begin
kx:=MyPoint[x].x+koef;
ky:=MyPoint[x].y+koef;
Form1.Canvas.Ellipse(kx,ky,kx+10,ky+10);
Form1.Canvas.TextOut(kx,ky-15,MyPoint[x].name);
end;
for a:=2 to 5 do
for b:=1 to a-1 do
if ((StringGrid1.Cells[b,a]<>'') and (StrtoInt(StringGrid1.Cells[b,a])>0)) then DrawLine (a,b,1);
end;
procedure TForm1.DrawLine(a1,a2,c: integer);
var
x1,y1,x2,y2:integer;
begin
if c=1 then Form1.Canvas.Pen.Color:=clBlack;
if c=2 t...
